D. Mathematical Problem

给定一个长度为 n(2n20) 的字符串,要求在中间加入 n2 个运算符号 +,× 求能得到的表达式的最小值。

直接分类讨论即可。要特判一下全是 1 的情况

void solve() {
    int n;cin >> n;
    string s;cin >> s;s = ' ' + s;
    int ans = 1e9;
    for (int i = 1;i < n;i++) {
        vector<int> a;
        for (int j = 1;j <= n;j++) {
            if (i != j) {
                a.push_back(s[j] - '0');
            } else {
                a.push_back((s[j] - '0') * 10 + s[j + 1] - '0');
                j++;
            }
        }
        int res = 0, ok = 1;
        for (int j = 0;j < a.size();j++) {
            if (a[j] == 0) {
                cout << "0\n";return;
            } else if (a[j] == 1) {
                res++;
            } else {
                ok = 0;
            }
        }
        ans = min(accumulate(a.begin(), a.end(), 0) - res + ok, ans);
    }
    cout << ans << '\n';
}